package code;


public class Stock {

	public int maxProfit(int kk,int[] prices){
		int ans=0;
		
		int days=prices.length;
		int maxTransactions=kk>days?days:kk;
		int[][] dp=new int[days][maxTransactions+1];
		int i,j,k;
		/*
		 * 初始化，dp[i][0]=0,0次交易的获得的利润都是0
		 */
		for(i=0;i<days;i++)
			dp[i][0]=0;
		/*
		 * 递推关系
		 * dp[i][k]=max(dp[j][k-1]):j<i
		 */
		for(i=1;i<maxTransactions+1;i++){
			for(j=0;j<days;j++){
				/*
				 * 枚举所有的k<j
				 */
				dp[j][i]=0;
				for(k=0;k<j;k++){
					if(k==0 && dp[j][i]<prices[j]-prices[k])
						dp[j][i]=prices[j]-prices[k];
					if(k>0 && dp[j][i]<dp[k-1][i-1]+prices[j]-prices[k])
						dp[j][i]=dp[k-1][i-1]+prices[j]-prices[k];
				}
			}
		}
		for(i=0;i<days;i++)
			for(j=0;j<=maxTransactions;j++)
				if(ans<dp[i][j])	
					ans=dp[i][j];
		
		return ans;
	}
	public static void main(String[] args){
		Stock stock=new Stock();
		int[] prices={1,2,3,4,5};
		int ans=stock.maxProfit(1, prices);
		System.out.println(ans);
		System.out.println(stock.maxProfit(2, prices));
	}
}
